{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Palindrome by Concatenating Two Letter Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表 #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestPalindrome"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #连接两字母单词得到的最长回文串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组&nbsp;<code>words</code>&nbsp;。<code>words</code>&nbsp;中每个元素都是一个包含 <strong>两个</strong>&nbsp;小写英文字母的单词。</p>\n",
    "\n",
    "<p>请你从 <code>words</code>&nbsp;中选择一些元素并按 <b>任意顺序</b>&nbsp;连接它们，并得到一个 <strong>尽可能长的回文串</strong>&nbsp;。每个元素 <strong>至多</strong>&nbsp;只能使用一次。</p>\n",
    "\n",
    "<p>请你返回你能得到的最长回文串的 <strong>长度</strong>&nbsp;。如果没办法得到任何一个回文串，请你返回 <code>0</code>&nbsp;。</p>\n",
    "\n",
    "<p><strong>回文串</strong>&nbsp;指的是从前往后和从后往前读一样的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>words = [\"lc\",\"cl\",\"gg\"]\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>一个最长的回文串为 \"lc\" + \"gg\" + \"cl\" = \"lcggcl\" ，长度为 6 。\n",
    "\"clgglc\" 是另一个可以得到的最长回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>words = [\"ab\",\"ty\",\"yt\",\"lc\",\"cl\",\"ab\"]\n",
    "<b>输出：</b>8\n",
    "<strong>解释：</strong>最长回文串是 \"ty\" + \"lc\" + \"cl\" + \"yt\" = \"tylcclyt\" ，长度为 8 。\n",
    "\"lcyttycl\" 是另一个可以得到的最长回文串。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>words = [\"cc\",\"ll\",\"xx\"]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>最长回文串是 \"cc\" ，长度为 2 。\n",
    "\"ll\" 是另一个可以得到的最长回文串。\"xx\" 也是。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= words.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>words[i].length == 2</code></li>\n",
    "\t<li><code>words[i]</code>&nbsp;仅包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-palindrome-by-concatenating-two-letter-words](https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-palindrome-by-concatenating-two-letter-words](https://leetcode.cn/problems/longest-palindrome-by-concatenating-two-letter-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"lc\",\"cl\",\"gg\"]', '[\"ab\",\"ty\",\"yt\",\"lc\",\"cl\",\"ab\"]', '[\"cc\",\"ll\",\"xx\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = {}\n",
    "        for word in words:\n",
    "            freq[word] = freq.get(word,0)+1\n",
    "        \n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "\n",
    "        for word, cnt in freq.items():\n",
    "            new_word = word[1]+word[0]\n",
    "            if new_word == word:\n",
    "                if cnt%2==1:\n",
    "                    mid = True\n",
    "                res += 2 * (cnt // 2 * 2)\n",
    "            elif word > new_word and new_word in freq:\n",
    "                res += 4 * min(freq[word],freq[new_word])\n",
    "        \n",
    "        if mid:\n",
    "            res+=2\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = [[0] * 26 for _ in range(26)]\n",
    "        for x, y in words:\n",
    "            cnt[ord(x) - ord('a')][ord(y) - ord('a')] += 1\n",
    "        odd = res = 0\n",
    "        for i in range(26):\n",
    "            c = cnt[i][i]\n",
    "            res += c - c % 2\n",
    "            odd |= c & 1\n",
    "            for j in range(i + 1, 26):\n",
    "                res += min(cnt[i][j], cnt[j][i]) * 2\n",
    "        return  (res + odd) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        def get_num(first, second):\n",
    "            return (ord(first) - 97) * 26 + ord(second) - 97\n",
    "\n",
    "        mid_cnt = 0\n",
    "        res = 0\n",
    "        num_dict = {}\n",
    "        for word in words:\n",
    "            if word[0] == word[1]:\n",
    "                mid_flag = True\n",
    "            else:\n",
    "                mid_flag = False\n",
    "\n",
    "            reverse_num = get_num(word[1], word[0])\n",
    "            if num_dict.get(reverse_num, 0) > 0:\n",
    "                res += 4\n",
    "                num_dict[reverse_num] -= 1\n",
    "                if mid_flag:\n",
    "                    mid_cnt -= 1\n",
    "            else:\n",
    "                num = get_num(word[0], word[1])\n",
    "                num_dict[num] = num_dict.get(num, 0) + 1\n",
    "                if mid_flag:\n",
    "                    mid_cnt += 1\n",
    "        \n",
    "        if mid_cnt > 0:\n",
    "            res += 2\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter(words)\n",
    "        ans = 0\n",
    "        mid = False\n",
    "        for word, count in cnt.items():\n",
    "            reversed_word = word[::-1]\n",
    "            if word == reversed_word:\n",
    "                if count % 2:\n",
    "                    mid = True\n",
    "                ans += 2 * (count // 2 * 2)\n",
    "            elif word > reversed_word:\n",
    "                ans += 4 * min(cnt[word], cnt[reversed_word])\n",
    "        if mid:\n",
    "            ans += 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        dic = {}\n",
    "        for w in words:\n",
    "            dic[w] = dic.get(w,0)+1\n",
    "        lens = 0\n",
    "        middle = 0\n",
    "        for w,num in dic.items():\n",
    "            rev = w[::-1]\n",
    "            if w==rev:\n",
    "                if num%2==1:\n",
    "                    middle=2\n",
    "                lens += 2*(num//2*2)\n",
    "            elif rev in words and w>rev:\n",
    "                lens += 4*(min(dic[w],dic[rev]))\n",
    "        return lens+middle\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        flag, res, d = False, 0, {}\n",
    "        for w in words:\n",
    "            nw = w[::-1]\n",
    "            if nw in d and d[nw] > 0:\n",
    "                d[nw] -= 1\n",
    "                res += 2\n",
    "            else:\n",
    "                d[w] = 1 if w not in d else d[w]+1\n",
    "        for k in d.keys():\n",
    "            if d[k] == 1 and k[0] == k[1]:\n",
    "                res += 1\n",
    "                break\n",
    "        return res*2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        d = Counter(words)\n",
    "        res = 0\n",
    "        f = False\n",
    "        l = list(d.keys())\n",
    "        for key in l:\n",
    "            v1 = d[key]\n",
    "            if key[0] == key[1]:\n",
    "                if v1 % 2 == 0:\n",
    "                    res += 2 * v1\n",
    "                else:\n",
    "                    if not f:\n",
    "                        res += 2 * v1\n",
    "                        f = True\n",
    "                    else:\n",
    "                        res += 2 * (v1 - 1)\n",
    "            else:\n",
    "                if key[::-1] in l:\n",
    "                    v2 = d[key[::-1]]\n",
    "                    res += 2 * min(v1, v2)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)\n",
    "        res = 0\n",
    "        mid = False # 是否含有中心单词\n",
    "        for word,cnt in freq.items():\n",
    "            rev_word = word[1] + word[0]\n",
    "            if word==rev_word:\n",
    "                if cnt%2==1:\n",
    "                    mid = True\n",
    "                res += cnt//2 * 4\n",
    "            else:\n",
    "                res += 2 * min(freq[word], freq[rev_word])\n",
    "\n",
    "        if mid:\n",
    "            res += 2\n",
    "\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        c = Counter()\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            if (target := w[::-1]) in c:\n",
    "                c[target] -= 1\n",
    "                if c[target] == 0:\n",
    "                    del c[target]\n",
    "                ans += 4\n",
    "            else:\n",
    "                c[w] += 1\n",
    "        \n",
    "        # 处理相等的情况\n",
    "        if any(w for w in c if w[0] == w[1]):\n",
    "            ans += 2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        check = {}\n",
    "        temp = 0\n",
    "        for i in range(len(words)):\n",
    "            if words[i][::-1] in check and check[words[i][::-1]] > 0:\n",
    "                check[words[i][::-1]] -= 1\n",
    "                ans += 2\n",
    "            else:\n",
    "                check[words[i]] = check.get(words[i], 0) + 1\n",
    "\n",
    "        for i in check:\n",
    "            if i == i[::-1] and check[i] == 1:\n",
    "                return (ans+1)*2 \n",
    "        return ans * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1] + word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "\n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：flix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        odd = 0\n",
    "        mp = Counter(words)\n",
    "        for word, cnt in mp.items():\n",
    "            if word[0] == word[1]:\n",
    "                ans += (cnt - cnt % 2) * 2\n",
    "                if cnt % 2:\n",
    "                    odd = 2\n",
    "            else:\n",
    "                ans += min(cnt, mp[word[1] + word[0]]) * 2\n",
    "        return ans + odd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        C = Counter()\n",
    "        for i in words:\n",
    "            a,b = i[0],i[1]\n",
    "            C[(a,b)] += 1\n",
    "        S = set()\n",
    "        mx = 0\n",
    "        res = 0\n",
    "        for comb,cnt in C.items():\n",
    "            a,b = comb\n",
    "            if a == b:\n",
    "                res += cnt//2 * 4\n",
    "                if cnt % 2:mx = 1\n",
    "            elif comb in S:continue\n",
    "            else:\n",
    "                S.add((b,a))\n",
    "                res += 4*min(cnt,C[(b,a)])\n",
    "        return res + mx*2\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter(words)\n",
    "        unique = list(cnt.keys())\n",
    "        ans = single = 0\n",
    "\n",
    "        for word in unique:\n",
    "            rev = word[::-1]\n",
    "            if word != rev:\n",
    "                add = min(cnt[word], cnt[rev])\n",
    "                ans += len(word) * 2 * add\n",
    "                cnt[word] -= add\n",
    "                cnt[rev] -= add\n",
    "            else:\n",
    "                add = cnt[word] // 2\n",
    "                ans += len(word) * 2 * add\n",
    "                cnt[word] -= 2 * add\n",
    "                if cnt[word]:\n",
    "                    single = single if single > len(word) else len(word)\n",
    "\n",
    "        return ans + single\n",
    "\n",
    "# 作者：liupengsay\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter()     \n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: \n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               \n",
    "                cnt[word] += 1\n",
    "        \n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[::-1]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if not mid and cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt >> 1 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter(words)\n",
    "        ans = single = 0\n",
    "        for w in list(cnt.keys()):\n",
    "            if w == w[::-1]:\n",
    "                x = cnt[w]//2\n",
    "                ans += x*4\n",
    "                if cnt[w] % 2:\n",
    "                    single = 2\n",
    "            else:\n",
    "                x = min(cnt[w], cnt[w[::-1]])\n",
    "                ans += x*4\n",
    "                cnt[w] -= x\n",
    "                cnt[w[::-1]] -= x\n",
    "        return ans + single\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        hashmap = {}           \n",
    "        for i in words:\n",
    "            if i not in hashmap:\n",
    "                hashmap[i] = 1\n",
    "            else:\n",
    "                hashmap[i] += 1\n",
    "        mid = 0\n",
    "        res = 0\n",
    "        flag = 0\n",
    "        for i in hashmap:\n",
    "            if i[0] == i[1]:\n",
    "                if hashmap[i] > 1 :\n",
    "                    mid += hashmap[i]//2\n",
    "                if hashmap[i]% 2 == 1:\n",
    "                    flag = 1\n",
    "            else:\n",
    "                i_ = i[1]+i[0]\n",
    "                if i_ in hashmap:\n",
    "                    res += min(hashmap[i],hashmap[i_])\n",
    "\n",
    "        return  2*(res + flag)+ 4*mid\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[::-1]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if not mid and cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt >> 1 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += min(freq[word], freq[rev]) << 2\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "        \n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                # print(rword,cnt[rword])\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "            # print(cnt,ans)\n",
    "        \n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        d=collections.Counter(words)\n",
    "        s=set()\n",
    "        flag=False\n",
    "        count=0\n",
    "        for ss in d:\n",
    "            if ss not in s:\n",
    "                if ss==ss[1]+ss[0]:\n",
    "                    if d[ss]%2==0:\n",
    "                        count+=d[ss]*2\n",
    "                    else:\n",
    "                        flag=True\n",
    "                        count+=(d[ss]//2*2)*2\n",
    "                     \n",
    "                else:\n",
    "                    l=min(d[ss],d[ss[::-1]])\n",
    "                    count+=l*4\n",
    "                s.add(ss)\n",
    "                s.add(ss[::-1])\n",
    "        if flag==True:\n",
    "            count+=2\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt % 2 == 1:\n",
    "                    mid = True\n",
    "                res += 2 * (cnt // 2 * 2)\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\r\n",
    "    #     # repeat: word为两个相同字母的个数\r\n",
    "    #     # no_repeat: 回文字符串word总个数\r\n",
    "    #     repeat_dit = {word: 0 for word in words if word[0] == word[1]}\r\n",
    "    #     flag_arr = [0 for _ in words]\r\n",
    "    #     repeat, no_repeat = 0, 0\r\n",
    "    #     for i, word in enumerate(words):\r\n",
    "    #         if flag_arr[i]:\r\n",
    "    #             continue\r\n",
    "    #         if word[0] == word[1]:\r\n",
    "    #             repeat += 1\r\n",
    "    #             repeat_dit[word] += 1\r\n",
    "    #             continue\r\n",
    "    #         for j, w in enumerate(words[i+1:]):\r\n",
    "    #             if flag_arr[j+i+1]:\r\n",
    "    #                 continue\r\n",
    "    #             if w[::-1] == word:\r\n",
    "    #                 flag_arr[i], flag_arr[j+i+1] = 1, 1\r\n",
    "    #                 no_repeat += 2\r\n",
    "    #                 break\r\n",
    "\r\n",
    "    #     odd, even = 0, 0  # 奇数，偶读   \r\n",
    "    #     for val in repeat_dit.values():\r\n",
    "    #         if val >= 2:\r\n",
    "    #             even += val if not val % 2 else val - 1\r\n",
    "    #             odd += 1 if val % 2 else 0\r\n",
    "    #         else:\r\n",
    "    #             odd += 1\r\n",
    "        \r\n",
    "    #     return no_repeat * 2 + even * 2 if not odd else no_repeat * 2 + even * 2 + 2\r\n",
    "\r\n",
    "    # *************************************************************************************************\r\n",
    "\r\n",
    "        counter = collections.Counter(words)\r\n",
    "        # flag:是否有单个回文word插入中间\r\n",
    "        length, flag = 0, False\r\n",
    "        for word, num in counter.items():\r\n",
    "            if word[0] == word[1]:\r\n",
    "                length += num // 2 * 4\r\n",
    "                if num % 2:\r\n",
    "                    flag = True\r\n",
    "            else:\r\n",
    "                reverse = word[1] + word[0]\r\n",
    "                length += min(num, counter[reverse]) * 2 if reverse in counter else 0\r\n",
    "        \r\n",
    "        return length + 2 if flag else length\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt >> 1 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt // 2 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter(words)\n",
    "        unique = list(cnt.keys())\n",
    "        ans = single = 0\n",
    "\n",
    "        for word in unique:\n",
    "            rev = word[::-1]\n",
    "            if word != rev:\n",
    "                add = min(cnt[word], cnt[rev])\n",
    "                ans += len(word) * 2 * add\n",
    "                cnt[word] -= add\n",
    "                cnt[rev] -= add\n",
    "            else:\n",
    "                add = cnt[word] // 2\n",
    "                ans += len(word) * 2 * add\n",
    "                cnt[word] -= 2 * add\n",
    "                if cnt[word]:\n",
    "                    single = single if single > len(word) else len(word)\n",
    "\n",
    "        return ans + single\n",
    "\n",
    "# 作者：liupengsay\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        same = collections.defaultdict(int)\n",
    "        other = collections.defaultdict(int)\n",
    "        for w in words:\n",
    "            if w[0] == w[1]:\n",
    "                same[w] += 1\n",
    "            else:\n",
    "                other[w] += 1\n",
    "        \n",
    "\n",
    "        res = 0\n",
    "        for key in other:\n",
    "            if other[key] > 0:\n",
    "                res += min(other[key], other.get(key[::-1], 0)) * 4\n",
    "                other[key] = 0\n",
    "                if key[::-1] in other:\n",
    "                    other[key[::-1]] = 0\n",
    "\n",
    "\n",
    "\n",
    "        flag = False\n",
    "        for key in same:\n",
    "            res += same[key] // 2 * 4\n",
    "\n",
    "            if same[key] % 2 == 1:\n",
    "                flag = True\n",
    "        \n",
    "        if flag:\n",
    "            return res + 2\n",
    "        else:\n",
    "            return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt % 2 == 1:\n",
    "                    mid = True\n",
    "                res += 2 * (cnt // 2 * 2)\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        n = len(words)\n",
    "        cnt = Counter(words)     \n",
    "        ans = 0\n",
    "        flag = False\n",
    "        for k, v in cnt.items():\n",
    "            if k[0] == k[1]:\n",
    "                if v % 2:\n",
    "                    flag = True\n",
    "                    ans += (v - 1) * 2\n",
    "                else:\n",
    "                    ans += v * 2\n",
    "            else:\n",
    "                y = k[::-1]\n",
    "                if y in cnt.keys():\n",
    "                    ans += min(v, cnt[y]) * 4 \n",
    "                    cnt[k] = 0\n",
    "                    cnt[y] = 0\n",
    "        return ans + (flag == True) * 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt=[[0 for _ in range(26)] for _ in range(26)]\n",
    "        #print(cnt)\n",
    "        ans=0\n",
    "        for _,s in enumerate(words):\n",
    "            cnt[ord(s[0])-ord('a')][ord(s[1])-ord('a')]+=1\n",
    "        odd=0\n",
    "        for i in range(26):\n",
    "            c=cnt[i][i]\n",
    "            ans+=c-c%2\n",
    "            odd|=c&1\n",
    "            for j in range(i+1,26):\n",
    "                ans+=min(cnt[i][j],cnt[j][i])*2\n",
    "        return (ans+odd)*2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if not mid and cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt >> 1 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        dp = [[0] * 26 for _ in range(26)]\n",
    "\n",
    "        for w in words:\n",
    "            i = ord(w[0]) - 97\n",
    "            j = ord(w[1]) - 97\n",
    "            dp[i][j] += 1\n",
    "\n",
    "        res = 0\n",
    "        flag = True\n",
    "        for i in range(26):\n",
    "            for j in range(i, 26):\n",
    "                if i == j and dp[i][j] > 0:\n",
    "                    if dp[i][j] % 2 == 1:\n",
    "                        flag = False\n",
    "                    res += dp[i][j] // 2 * 4\n",
    "                elif i != j:\n",
    "                    res += min(dp[i][j], dp[j][i]) * 4\n",
    "\n",
    "        if flag:\n",
    "            return res\n",
    "        else:\n",
    "            return res + 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        words_map = defaultdict(int)\n",
    "        \n",
    "        res = 0\n",
    "        for word in words:\n",
    "            words_map[word] += 1\n",
    "            \n",
    "        for k in words_map:\n",
    "            if k[::-1] in words_map and k[0] != k[1]:\n",
    "                temp = min(words_map[k], words_map[k[::-1]])\n",
    "                res = res + temp * 4\n",
    "                words_map[k] -= temp\n",
    "                words_map[k[::-1]] -= temp\n",
    "            \n",
    "            if k[0] == k[1]:\n",
    "                res = res + (words_map[k] // 2) * 4\n",
    "        \n",
    "        for k in words_map:\n",
    "            if k[0] == k[1] and words_map[k] % 2 == 1:\n",
    "                res += 2\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1] + word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "\n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "\n",
    "        return ans\n",
    "\n",
    "# 作者：flix\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        from collections import Counter\n",
    "\n",
    "        str_cnt = Counter(words)\n",
    "        single = False\n",
    "        res = 0\n",
    "        for s, c in str_cnt.items():\n",
    "            if s[0] == s[1]:\n",
    "                res += str_cnt[s]//2 * 4\n",
    "                if str_cnt[s]%2 == 1:\n",
    "                    single = True\n",
    "            elif s[0] < s[1]:\n",
    "                if s[1]+s[0] in str_cnt:\n",
    "                    res += min(str_cnt[s], str_cnt[s[1]+s[0]]) * 4\n",
    "        \n",
    "        if single:\n",
    "            res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt, dflag, dct = 0, True, Counter(words)\n",
    "        for w in dct:\n",
    "            if w[0] < w[1]:\n",
    "                if w[::-1] in dct: cnt += min(dct[w], dct[w[::-1]])\n",
    "            elif w[0] == w[1]:\n",
    "                cnt += dct[w] >> 1\n",
    "                if dflag and dct[w] & 1: dflag = False\n",
    "        return (cnt << 2) + (0 if dflag else 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        cnt, dflag, dct = 0, True, Counter(words)\n",
    "        for w in dct:\n",
    "            if w[0] < w[1]:\n",
    "                if w[::-1] in dct: cnt += min(dct[w], dct[w[::-1]])\n",
    "            elif w[0] == w[1]:\n",
    "                cnt += dct[w] >> 1\n",
    "                if dflag and dct[w] & 1: dflag = False\n",
    "        return (cnt << 2) + (0 if dflag else 2)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "        \n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        xf = collections.Counter(words)\n",
    "        \n",
    "        res = 0\n",
    "        odd = 0\n",
    "        \n",
    "        for x in xf.keys():\n",
    "            f = xf[x]\n",
    "            if x == x[::-1]:\n",
    "                if f % 2 == 0:\n",
    "                    res += f * 2\n",
    "                else:\n",
    "                    res += (f - 1) * 2\n",
    "                    odd += 1\n",
    "            else:\n",
    "                y = x[::-1]\n",
    "                if y in xf:\n",
    "                    f2 = xf[y]\n",
    "                    res += 4 * min(f, f2)\n",
    "                    xf[x] = 0\n",
    "                    xf[y] = 0\n",
    "                \n",
    "        if odd > 0:\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        flag = False\n",
    "        res = 0\n",
    "        dict = {}\n",
    "        for word in words:\n",
    "            nw = word[1] + word[0]\n",
    "            if nw in dict and dict[nw] > 0:\n",
    "                dict[nw] -= 1\n",
    "                res += 2\n",
    "            else:\n",
    "                if word in dict:\n",
    "                    dict[word] += 1\n",
    "                else:\n",
    "                    dict[word] = 1\n",
    "        for key in dict.keys():\n",
    "            if dict[key] == 1 and key[0] == key[1]:\n",
    "                res += 1\n",
    "                break\n",
    "        return res*2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        special = {}\n",
    "        vis = {}\n",
    "        for word in words:\n",
    "            re_word = word[::-1]\n",
    "            if re_word in vis and vis[re_word] > 0:\n",
    "                ans += 4\n",
    "                vis[re_word] -= 1\n",
    "            else:\n",
    "                if word not in vis:\n",
    "                    vis[word] = 0\n",
    "                vis[word] += 1\n",
    "            if word == re_word:\n",
    "                if word not in special:\n",
    "                    special[word] = 0\n",
    "                special[word] += 1  \n",
    "\n",
    "        for val in special.values():\n",
    "            if val % 2 == 1:\n",
    "                ans += 2\n",
    "                break      \n",
    "        return ans        \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "        \n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        \n",
    "        cnt = Counter()     # 哈希表，记录未匹配得word出现的次数\n",
    "        ans = 0\n",
    "\n",
    "        # 遍历words，对于每个word看是否能匹配到其配对的回文串rword\n",
    "        for word in words:\n",
    "            rword = word[1]+word[0]\n",
    "            if cnt[rword] >= 1: # rword存在，且未被word匹配\n",
    "                cnt[rword] -= 1\n",
    "                ans += 4\n",
    "            else:               # 否则，记录当前word\n",
    "                cnt[word] += 1\n",
    "        \n",
    "        # 对于本身即为回文串的word，判断是否还剩余有未匹配的 【最多只能加一个】\n",
    "        for word in cnt:\n",
    "            if word[0] == word[1] and cnt[word] >= 1:\n",
    "                ans += 2\n",
    "                break\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)   # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt & 1:\n",
    "                    mid = True\n",
    "                res += cnt >> 1 << 2\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        # # official\n",
    "        # import collections\n",
    "        # freq_dic = collections.Counter(words)\n",
    "        # num_pairs = 0\n",
    "        # center = False\n",
    "        # for wor, count in freq_dic.items():\n",
    "        #     if word[0] == word[1]:\n",
    "        #         if freq_dic[word] % 2 == 0:\n",
    "        #             num_pairs\n",
    "\n",
    "\n",
    "        # self\n",
    "        import collections\n",
    "        freq_dic = collections.Counter(words)\n",
    "        num_pairs = 0\n",
    "        center = False\n",
    "        for word, count in freq_dic.items():\n",
    "            if word[0] == word[1]:\n",
    "                if freq_dic[word] % 2 == 0:\n",
    "                    num_pairs += count\n",
    "                else:\n",
    "                    if not center:\n",
    "                        num_pairs += count\n",
    "                        center = True\n",
    "                    else:\n",
    "                        num_pairs += count - 1\n",
    "            else:\n",
    "                word_rev = word[1] + word[0]\n",
    "                if freq_dic[word_rev] != 0:\n",
    "                    num_pairs += min(count, freq_dic[word_rev]) * 2\n",
    "                    freq_dic[word] = 0\n",
    "        return num_pairs * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        i=0\n",
    "        num=0\n",
    "        new=[]\n",
    "        newx=[]\n",
    "        for i in range (len(words)):\n",
    "            if words[i][0]==words[i][1]:\n",
    "                newx.append(words[i])\n",
    "            else:\n",
    "                new.append(words[i])\n",
    "\n",
    "        lenx=0\n",
    "        lx=[[x,newx.count(x)] for x in set(newx)]\n",
    "        oddn=0\n",
    "        for s in lx:\n",
    "            if s[1]%2==1 and oddn<1:\n",
    "                lenx+=s[1]*2\n",
    "                oddn+=1\n",
    "                \n",
    "            elif s[1]%2==1 and oddn>=1:\n",
    "                lenx+=(s[1]-1)*2\n",
    "            elif s[1]%2==0:\n",
    "                lenx+=s[1]*2\n",
    "            print('lenx',lenx)\n",
    "        #print('new',new,'newx: ',newx)\n",
    "        lx2={x:new.count(x) for x in set(new)}\n",
    "\n",
    "        #print('lx2',lx2)\n",
    "        kall=[]\n",
    "        for k,v in lx2.items():\n",
    "            kr=k[1]+k[0]\n",
    "            if kr in lx2.keys() and kr not in kall:\n",
    "                addx=min(v,lx2[kr])\n",
    "                print(v,lx2[kr],addx)\n",
    "                kall.append(k)\n",
    "                lenx+=4*addx\n",
    "         \n",
    "        return lenx\n",
    "       \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq = Counter(words)  # 单词出现次数\n",
    "        res = 0   # 最长回文串长度\n",
    "        mid = False   # 是否含有中心单词\n",
    "        for word, cnt in freq.items():\n",
    "            # 遍历出现的单词，并更新长度\n",
    "            rev = word[1] + word[0]   # 反转后的单词\n",
    "            if word == rev:\n",
    "                if cnt % 2 == 1:\n",
    "                    mid = True\n",
    "                res += 2 * (cnt // 2 * 2)\n",
    "            elif word > rev:   # 避免重复遍历\n",
    "                res += 4 * min(freq[word], freq[rev])\n",
    "        if mid:\n",
    "            # 含有中心单词，更新长度\n",
    "            res += 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        hashmap = dict()\n",
    "        for i in words:\n",
    "            if i in hashmap:\n",
    "                hashmap[i] += 1\n",
    "            else:\n",
    "                hashmap[i] = 1\n",
    "        match = 0\n",
    "        for i in hashmap:\n",
    "            if i[::-1] in hashmap and i[0] != i[1]:\n",
    "                m = min(hashmap[i], hashmap[i[::-1]])\n",
    "                hashmap[i] -= m\n",
    "                hashmap[i[::-1]] -= m\n",
    "                match += m*4\n",
    "            if i[0] == i[1]:\n",
    "                m = hashmap[i] - hashmap[i] % 2\n",
    "                hashmap[i] -= m\n",
    "                match += m*2\n",
    "        for i in hashmap:\n",
    "            if i[0] == i[1]:\n",
    "                if hashmap[i] == 1:\n",
    "                    return match + 2\n",
    "        return match\n",
    "        #print(hashmap,match)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        counters=collections.Counter(words)\n",
    "        res=0\n",
    "        flag=0\n",
    "        for word,counter in counters.items():\n",
    "            rev=word[1::-1]\n",
    "            if word == rev:\n",
    "                if counter%2==1:\n",
    "                    flag=1\n",
    "                res+= 4*(counter//2)\n",
    "            elif word > rev:\n",
    "                res+= 4*min(counters[word],counters[rev])\n",
    "        if flag:res+=2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        freq=collections.Counter(words)\n",
    "        flag=False\n",
    "        ans=0\n",
    "        for s,cnt in freq.items():\n",
    "            rev=s[::-1]\n",
    "            if s==rev:\n",
    "                ans+=2*(cnt//2*2)\n",
    "                if cnt%2:\n",
    "                    flag=True\n",
    "            elif s>rev:\n",
    "                ans+=4*min(freq[rev],cnt)\n",
    "        if flag:\n",
    "            ans+=2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        dic = {}\n",
    "        length = 0\n",
    "        special = 0\n",
    "        for char in words:\n",
    "            #print(dic)\n",
    "            new_char = char[1]+char[0]\n",
    "            if new_char == char:\n",
    "                special +=1              \n",
    "                \n",
    "            if char in dic and dic[char]>0:\n",
    "                if new_char == char:\n",
    "                    special -=2\n",
    "                dic[char] -= 1\n",
    "                length += 4\n",
    "            else:\n",
    "                dic[new_char] = dic.get(new_char,0) + 1\n",
    "\n",
    "        if special>0:\n",
    "            length += 2\n",
    "        return length\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        i=0\n",
    "        num=0\n",
    "        new=[]\n",
    "        newx=[]\n",
    "        for i in range (len(words)):\n",
    "            if words[i][0]==words[i][1]:\n",
    "                newx.append(words[i])\n",
    "            else:\n",
    "                new.append(words[i])\n",
    "\n",
    "        lenx=0\n",
    "        lx=[[x,newx.count(x)] for x in set(newx)]\n",
    "        oddn=0\n",
    "        for s in lx:\n",
    "            if s[1]%2==1 and oddn<1:\n",
    "                lenx+=s[1]*2\n",
    "                oddn+=1\n",
    "                \n",
    "            elif s[1]%2==1 and oddn>=1:\n",
    "                lenx+=(s[1]-1)*2\n",
    "            elif s[1]%2==0:\n",
    "                lenx+=s[1]*2\n",
    "            print('lenx',lenx)\n",
    "        #print('new',new,'newx: ',newx)\n",
    "        lx2={x:new.count(x) for x in set(new)}\n",
    "\n",
    "        #print('lx2',lx2)\n",
    "        kall=[]\n",
    "        for k,v in lx2.items():\n",
    "            kr=k[1]+k[0]\n",
    "            if kr in lx2.keys() and kr not in kall:\n",
    "                addx=min(v,lx2[kr])\n",
    "                print(v,lx2[kr],addx)\n",
    "                kall.append(k)\n",
    "                lenx+=4*addx\n",
    "         \n",
    "        return lenx\n",
    "       \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        import collections\n",
    "        freq_dic = collections.Counter(words)\n",
    "        num_pairs = 0\n",
    "        center = False\n",
    "        for word, count in freq_dic.items():\n",
    "            if word[0] == word[1]:\n",
    "                if freq_dic[word] % 2 == 0:\n",
    "                    num_pairs += freq_dic[word]\n",
    "                else:\n",
    "                    if not center:\n",
    "                        num_pairs += freq_dic[word]\n",
    "                        center = True\n",
    "                    else:\n",
    "                        num_pairs += freq_dic[word] - 1\n",
    "            else:\n",
    "                word_rev = word[1] + word[0]\n",
    "                if freq_dic[word_rev] != 0:\n",
    "                    num_pairs += min(freq_dic[word], freq_dic[word_rev]) * 2\n",
    "                    freq_dic[word] = 0\n",
    "        return num_pairs * 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        new=[]\n",
    "        newx=[]\n",
    "        for i in range (len(words)):\n",
    "            if words[i][0]==words[i][1]:\n",
    "                newx.append(words[i])\n",
    "            else:\n",
    "                new.append(words[i])\n",
    "\n",
    "        lenx=0\n",
    "        lx=[[x,newx.count(x)] for x in set(newx)]\n",
    "        oddn=0\n",
    "        for s in lx:\n",
    "            if s[1]%2==1 and oddn<1:\n",
    "                lenx+=s[1]*2\n",
    "                oddn+=1\n",
    "                \n",
    "            elif s[1]%2==1 and oddn>=1:\n",
    "                lenx+=(s[1]-1)*2\n",
    "            elif s[1]%2==0:\n",
    "                lenx+=s[1]*2\n",
    "            print('lenx',lenx)\n",
    "        #print('new',new,'newx: ',newx)\n",
    "        lx2={x:new.count(x) for x in set(new)}\n",
    "\n",
    "        #print('lx2',lx2)\n",
    "        kall=[]\n",
    "        for k,v in lx2.items():\n",
    "            kr=k[1]+k[0]\n",
    "            if kr in lx2.keys() and kr not in kall:\n",
    "                addx=min(v,lx2[kr])\n",
    "                print(v,lx2[kr],addx)\n",
    "                kall.append(k)\n",
    "                lenx+=4*addx\n",
    "         \n",
    "        return lenx\n",
    "       \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestPalindrome(self, words: List[str]) -> int:\n",
    "        a={}\n",
    "        b={}\n",
    "        c={}\n",
    "        for i in words:\n",
    "            if i[0]==i[1]:\n",
    "                if i in c:\n",
    "                    c[i]+=1\n",
    "                else:\n",
    "                    c[i]=1\n",
    "            elif i[0]<i[1]:\n",
    "                if i in a:\n",
    "                    a[i]+=1\n",
    "                else:\n",
    "                    a[i]=1\n",
    "            else:\n",
    "                if i in b:\n",
    "                    b[i]+=1\n",
    "                else:\n",
    "                    b[i]=1\n",
    "            \n",
    "        ans=0\n",
    "        \n",
    "        e=0\n",
    "        for i in c:\n",
    "            if e==0 and c[i]%2==1:\n",
    "                ans+=c[i]\n",
    "                e=1\n",
    "            else:\n",
    "                ans+=c[i]//2*2\n",
    "            \n",
    "        for i in a:\n",
    "            if i[::-1] in b:\n",
    "                ans+=min(a[i],b[i[::-1]])*2\n",
    "        return ans*2\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
